#include "stringMatch.h"

#include <stdio.h>

#define STR_LENGTH 22
#define PATTERN_LENGTH 5

// 计算出最大公共前后缀长度数组
void getNext(const char pattern[], int next[]) {
    int i = 1, j = 0;
    next[0] = 0;
    while (i < PATTERN_LENGTH - 1) {
        if (pattern[i] == pattern[j]) {
            j++;
            next[i] = j;
            i++;
        } else {
            if (j > 0) {
                j = next[j - 1];
            } else {
                next[i] = j;
                i++;
            }
        }
    }

    // 为了后面的匹配，需要把元素整体往后移动一位，空位用-1填补
    for (int n = PATTERN_LENGTH - 2; n > 0; n--) {
        next[n] = next[n - 1];
    }
    next[0] = -1;
}

void kmpMatch(const char str[], const char pattern[], int result[]) {
    int next[PATTERN_LENGTH - 1];
    getNext(pattern, next);
    printf("next 数组：");
    for (int i = 0; i < PATTERN_LENGTH - 1; ++i) {
        printf("%d,", next[i]);
    }
    printf("\n");

    int n = 0;
    int i = 0;
    int x = 0;
    int t = 0;
    while (PATTERN_LENGTH - i < STR_LENGTH - n) {
        t++;
        if (pattern[i] == str[n]) {
            // 匹配到最后一个元素, 存入result中, 并继续找下一个
            if (i == PATTERN_LENGTH - 2) {
                result[x++] = n - i;
                i = next[i];
            } else {
                i++;
                n++;
            }
        } else {
            i = next[i];
            if (i == -1) {
                i++;
                n++;
            }
        }
    }
    result[x] = -1;

    printf("循环次数: %d\n", t);
}

void kmpMatchTest() {
    char str[STR_LENGTH] = "BBCABCDABABCDABCDABDE";
    char pattern[PATTERN_LENGTH] = "ABCD";

    int result[PATTERN_LENGTH - 1];

    printf("字符串：%s\n",str);
    printf("匹配子串：%s\n",pattern);

    kmpMatch(str, pattern, result);

    printf("匹配到位置为：");
    for (int i = 0; i < PATTERN_LENGTH - 1 && result[i] != -1; ++i) {
        printf("%d,", result[i]);
    }
    printf("\n");
}